package com.bear.bearalgo.双向队列;

/* 基于环形数组实现的双向队列 */
class ArrayDeque {
    private int[] nums;//用于存储双向队列元素的数组
    private int front;//队首指针，指向队首元素
    private int queSize;//双向队列长度

    /**
     * 构造方法
     */
    public ArrayDeque(int capacity) {
        this.nums = new int[capacity];
        front = queSize = 0;
    }

    /**
     * 获取双向队列的容量
     */
    public int capacity() {
        return nums.length;
    }

    /**
     * 获取双向队列的长度
     */
    public int size() {
        return queSize;
    }

    /**
     * 判断双向队列是否为空
     */
    public boolean isEmpty() {
        return size() == 0;
    }


    /**
     * 计算环形数组索引
     */
    private int index(int i) {
        //通过取余操作实现数组首尾相连
        //当i越过数组尾部后，回到头部
        //当越过数组头部后，回到尾部
        return (i + capacity()) % capacity();
    }


    /**
     * 队首入队
     */
    public void pushFirst(int num) {
        if (size() == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        //队首指针向左移动一位
        //通过取余操作实现front越过数组头部后回到尾部
        front = index(front - 1);
        //将num添加到队首
        nums[front] = num;
        queSize++;
    }

    /**
     * 队尾入队
     */
    public void pushLast(int num) {
        if (size() == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        //计算队尾指针，指向队尾索引+1
        int rear = index(front + queSize);
        //将num添加到队尾
        nums[rear] = num;
        queSize++;
    }


    /**
     * 访问队首元素
     */
    public int peekFirst() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        return nums[front];
    }

    /**
     * 队首出队
     */
    public int popFirst() {
        int num = peekFirst();
        //队首指针向后移动一位
        front = index(front + 1);
        queSize--;
        return num;
    }


    /**
     * 访问队尾元素
     */
    public int peekLast() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        return nums[index(front + queSize - 1)];
    }

    /**
     * 队尾出队
     */
    public int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    /**
     * 返回数组用于打印
     */
    public int[] toArray() {
        int[] arr = new int[size()];
        for (int i = 0, j = front; i < size(); i++, j++) {
            arr[i] = nums[index(j)];
        }
        return arr;
    }

    public static void main(String[] args) {
        // 创建一个容量为 5 的双向队列
        ArrayDeque deque = new ArrayDeque(5);

        // 队首入队
        deque.pushFirst(1);
        System.out.println("队首入队 1 后，队列元素: " + arrayToString(deque.toArray()));

        // 队尾入队
        deque.pushLast(2);
        System.out.println("队尾入队 2 后，队列元素: " + arrayToString(deque.toArray()));

        // 队首入队
        deque.pushFirst(3);
        System.out.println("队首入队 3 后，队列元素: " + arrayToString(deque.toArray()));

        // 队尾入队
        deque.pushLast(4);
        System.out.println("队尾入队 4 后，队列元素: " + arrayToString(deque.toArray()));

        // 访问队首元素
        System.out.println("当前队首元素: " + deque.peekFirst());

        // 访问队尾元素
        System.out.println("当前队尾元素: " + deque.peekLast());

        // 队首出队
        int firstOut = deque.popFirst();
        System.out.println("队首出队元素: " + firstOut + "，出队后队列元素: " + arrayToString(deque.toArray()));

        // 队尾出队
        int lastOut = deque.popLast();
        System.out.println("队尾出队元素: " + lastOut + "，出队后队列元素: " + arrayToString(deque.toArray()));

        // 获取队列长度
        System.out.println("当前队列长度: " + deque.size());

        // 判断队列是否为空
        System.out.println("当前队列是否为空: " + deque.isEmpty());
    }

    private static String arrayToString(int[] array) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < array.length; i++) {
            sb.append(array[i]);
            if (i < array.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}